The present invention relates to associative search engines (ASEs) and, more particularly, to a method and device for significantly increasing the storage capacity of any Associative Search Engine by means of one or more external memories, and for performing fast search operations in these memories.
It is known that a large storage capacity is required for data packet classification and forwarding, in which large amounts of information must be stored in the information base. Storage space limitations affect all state-of-the-art ASEs, including Content Addressable Memories (CAMs) such as Binary CAMs and Ternary CAMs. Storage space limitation is also a key issue in the Range Search Engine (RSE) technology of HyWire Ltd., which is used for searching Multi-Dimensional Keys in Multi-Dimensional Ranges.
In the key search operations performed in the RAM-Based CAMs and Multi-RAM CAM configurations covered in all the above patents, it was assumed that once a specific row of a RAM or Multi-RAM is identified in the FC-Register, the entire row can be read out and all the key entries listed in the row can be simultaneously compared with the searched key using one or several Column Locators to identify the matching key. This may hold for SRAMs or other fast memory devices embedded in the RSE, where many cells (or many words) can be simultaneously accessed; however, this is not the case with external memory devices. This technology requires that a high-bandwidth memory device be embedded in the RSE, such that a large plurality of cells (or words) can be simultaneously accessed.
External memory devices would appear to be fundamentally inappropriate for the RSE technology. The bandwidth, which is given by the product of the device operating frequency and the number of bits retrieved per read access, specifies the bit rate transferred between an external memory device and the RSE, and must be large enough to meet the requirements of the lookup rate.
The use of an external memory with an Associative Search Engine is known, particularly in algorithmic implementations. The utilization of an external memory with a CAM-based ASE is also known. However, given the requisite lookup rates in data packet classification and forwarding applications, these technologies are bandwidth limited. Moreover, the requisite lookup rates have been steadily increasing, such that in the future, the bandwidth limitations will be even more acute.
It must be emphasized that these bandwidth limitations exist even when the relatively sophisticated and expensive Static Random Access Memories (SRAMs) are used as external memory. While Dynamic Random Access Memories (DRAMs) are typically much less inexpensive and consume significantly less power than SRAMs, DRAMs are much slower than SRAMs and require a refresh interval between consecutive accesses. These drawbacks, along with the relatively small number of bits that can be retrieved per access, limit the use of external DRAMS to low lookup rates.
There is therefore a recognized need for, and it would be highly advantageous to have, an Associative Search Engine that achieves high lookup rates and, at the same time, enables an increased storage capacity using an external memory. It would be of further advantage to have an ASE that is more economical than ASEs known heretofore, and more particularly, to have an ASE that utilizes standard, inexpensive external memory components having characteristically low energy consumption.